package ru.amse.stroganova.algorythms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import ru.amse.stroganova.graph.AbstractGraph;
import ru.amse.stroganova.graph.Edge;
import ru.amse.stroganova.graph.Vertex;

/**
 * Presents depth first search algorythm.
 * 
 * @author Dasha Stroganova
 *
 */
public class DFS {
	
	private final List<Vertex> reachableVertices;
	
	private final Map<Vertex, Boolean> wasVisited;
	
	private final Map<Vertex, Vertex> predesessors;
	
	private final Set<Edge> paths;
	
	private final AbstractGraph graph;
	
	/**
	 * Creates new dfs.
	 * @param graph 
	 *
	 */
	public DFS(AbstractGraph graph) {
		reachableVertices = new ArrayList<Vertex>();
		wasVisited = new HashMap<Vertex, Boolean>();
		predesessors = new HashMap<Vertex, Vertex>();
		paths = new HashSet<Edge>();
		this.graph = graph;
	}
	
	/**
	 * Finds all reachable vertices from the given one
	 * 
	 * @param vertex
	 * @return reachable vertices
	 */
	public List<Vertex> findReachableVertices(Vertex vertex) {
		reachableVertices.clear();
		wasVisited.clear();
		simpleDFS(vertex, null);
		return reachableVertices;
	}
	
	/**
	 * Finds all paths between two vertices
	 * 
	 * @param source
	 * @param sink
	 * @return paths
	 */
	public Set<Edge> findAllPaths(Vertex source, Vertex sink) {
		reachableVertices.clear();
		wasVisited.clear();
		simpleDFS(source, sink);
		for (Vertex vertex : reachableVertices) {
			for (Edge edge : vertex.getOutgoingEdges()) {
				if (edge.getDestination().equals(sink)) {
					paths.add(edge);
					continue;
				}
				if (!paths.contains(edge) && laysOnAPathToVertex(edge, sink)) {
					paths.add(edge);
				}
			}
		}
		return paths;
	}
	
	private boolean laysOnAPathToVertex(Edge edge, Vertex sink) {
		wasVisited.clear();
		predesessors.clear();
		return dfs(edge.getDestination(), sink);
	}
	
	private boolean dfs(Vertex vertex, Vertex destin) {
		boolean hadDestin = false;
		wasVisited.put(vertex, true);
		for (Edge edge : vertex.getOutgoingEdges()) {
			Vertex opposite = edge.getOppositeVertex(vertex);
			if (wasVisited.get(opposite) == null) {
				predesessors.put(opposite, vertex);
				if (opposite.equals(destin)) {
					for (Vertex currVertex = opposite; predesessors.get(currVertex) != null; currVertex = predesessors.get(currVertex)) {
						paths.add(graph.getConnectingEdge(predesessors.get(currVertex), currVertex));
					}
					return true;
				}
				hadDestin |= dfs(opposite, destin);
			}
		}
		return hadDestin;
	}
	
	private void simpleDFS(Vertex vertex, Vertex sink) {
		wasVisited.put(vertex, true);
		reachableVertices.add(vertex);
		for (Edge edge : vertex.getOutgoingEdges()) {
			Vertex opposite = edge.getOppositeVertex(vertex);
			if ((wasVisited.get(opposite) == null) && !opposite.equals(sink)) {
				simpleDFS(opposite, sink);
			}
		}
	}
}
